/**
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他
 * https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 * 思路：使用双端队列
 */
class LevelOrderThree {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque=new LinkedList<>();
        List<List<Integer>> ret=new ArrayList<>();
        int count=0;
        if(root==null){
            return ret;
        }
        deque.offerLast(root);
        while(!deque.isEmpty()){
            int size=deque.size();
            List<Integer> list=new ArrayList<>();
            if(count%2==0){
                for(int i=0;i<size;i++){
                    root=deque.pollFirst();
                    list.add(root.val);
                    if(root.left!=null){
                        deque.offerLast(root.left);
                    }
                    if(root.right!=null){
                        deque.offerLast(root.right);
                    }
                }
                ret.add(list);
            }else{
                for(int i=0;i<size;i++){
                    root=deque.pollLast();
                    list.add(root.val);
                    if(root.right!=null){
                        deque.offerFirst(root.right);
                    }
                    if(root.left!=null){
                        deque.offerFirst(root.left);
                    }
                }
                ret.add(list);
            }
            count++;
        }
        return ret;
    }
}